#include <bits/stdc++.h>

using namespace std;

/**
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int>> &matrix, int target)
{
    // write your code here
    //二分法，需要考虑超出取值范围、行与行之间的空隙和同行里列与列之间的空隙，同时需要随着二分变化记录二分法的起点和终点
    if(matrix.size() == 0)
        return false;
    int m = matrix.size(), n = matrix[0].size();
    int row = m / 2, line = n / 2, rowstart = 0, linestart = 0, rowend = m, lineend = n, temp;
    if(matrix[0][0] > target || matrix[m - 1][n - 1] < target)
        return false;
    while(matrix[row][line] != target)
    {
        if(matrix[row][0] > target){
            if(row >= 1 && matrix[row - 1][n - 1] < target)
                return false;
            temp = row;
            row = (rowstart + row) / 2;
            rowend = temp;
        }
        else if(matrix[row][n - 1] < target){
            if(row < m - 1 && matrix[row + 1][0] > target)
                return false;
            temp = row;
            row = (row + rowend) / 2;
            rowstart = temp;
        }
        else if(matrix[row][line] > target)
        {
            if(line >= 1 && matrix[row][line - 1] < target)
                return false;
            temp = line;
            line = (line + linestart) / 2;
            lineend = temp;
        }
        else
        {
            if(line < n - 1 && matrix[row][line + 1] > target)
                return false;
            temp = line;
            line = (line + lineend) / 2;
            linestart = temp;
        }
//        printf("%d\t%d\t%d\t%d\t%d\t%d\n", row, line, rowstart, linestart, rowend, lineend);
//        getchar();
    }
    return true;
}

int main()
{
//    vector<vector<int>> matrix = {
//        {1, 3, 5, 7},
//        {10, 11, 16, 20},
//        {23, 30, 34, 50}
//    };
//    vector<vector<int>> matrix = {};
    vector<vector<int>> matrix = {
        {1,4,8,15,20,22,25,32,36,43,49,51,53,55,59,65,69,73,80},
        {100,116,136,148,169,188,207,222,245,266,283,299,323,347,363,384,406,431,447},
        {460,477,494,512,532,548,562,582,604,617,630,643,663,675,690,713,735,758,783},
        {805,819,839,855,868,878,890,909,927,941,961,971,985,1000,1024,1037,1061,1086,1101},
        {1124,1135,1157,1182,1198,1221,1235,1254,1267,1277,1294,1319,1342,1361,1382,1400,1419,1440,1453},
        {1472,1495,1517,1542,1554,1567,1588,1603,1625,1642,1661,1680,1690,1702,1713,1725,1748,1771,1793}
    };
    printf("%d\n", searchMatrix(matrix, 81));
    printf("%d\n", searchMatrix(matrix, 1454));
    printf("%d\n", searchMatrix(matrix, 3));
    printf("%d\n", searchMatrix(matrix, 1));
    printf("%d\n", searchMatrix(matrix, 50));
    printf("%d\n", searchMatrix(matrix, 0));
    printf("%d\n", searchMatrix(matrix, 60));
    printf("%d\n", searchMatrix(matrix, 2));
    printf("%d\n", searchMatrix(matrix, 32));
    return 0;
}

        /**


        写出一个高效的算法来搜索 m × n矩阵中的值。

        这个矩阵具有以下特性：

            每行中的整数从左到右是排序的。
            每行的第一个数大于上一行的最后一个整数。

        您在真实的面试中是否遇到过这个题？
        样例

        考虑下列矩阵：

        [
          [1, 3, 5, 7],
          [10, 11, 16, 20],
          [23, 30, 34, 50]
        ]

        给出 target = 3，返回 true
        */
